package cn.xiaolang.function.data_structure;

/**
 * 字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。
 * 比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。
 * 你可以假设字符串中只包含大小写英文字母（a至z）。
 * <p>
 * 示例1:
 * <p>
 * 输入："aabcccccaaa"
 * 输出："a2b1c5a3"
 * 示例2:
 * <p>
 * 输入："abbccd"
 * 输出："abbccd"
 * 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
 * 提示：
 * <p>
 * 字符串长度在[0, 50000]范围内。
 * <p>
 *
 * @author fuhw/Dean
 * @date 2020-06-12
 */
public class No5CompressString {

    public static void main(String[] args) {
        System.out.println(compressString("aabcccccaaa"));
    }

    /**
     * 思路：
     * 遍历字符串时上面的代码改成先char[] c = S.toCharArray()再索引效率更高，
     * 通过s.charAt(i)方法索引多了方法栈和越界检查的消耗
     * <p>
     * 32 / 32 个通过测试用例
     * 状态：通过
     * 执行用时：3 ms
     * 内存消耗：39.5 MB
     */
    public static String compressString(String target) {
        if (target.isEmpty()) {
            return target;
        }
        char[] chars = target.toCharArray();
        StringBuilder stringBuilder = new StringBuilder();
        int temp = 1;
        for (int i = 0; i < chars.length - 1; i++) {
            if (chars[i] == chars[i + 1]) {
                temp++;
            } else {
                stringBuilder.append(chars[i]).append(temp);
                temp = 1;
            }
        }
        stringBuilder.append(chars[chars.length - 1]).append(temp);
        String result = stringBuilder.toString();
        return result.length() >= chars.length ? target : result;
    }

    /**
     * 32 / 32 个通过测试用例
     * 状态：通过
     * 执行用时：7 ms
     * 内存消耗：39.7 MB
     */
    public static String compressStringNoArray(String target) {
        if (target.isEmpty()) {
            return target;
        }
        StringBuilder stringBuilder = new StringBuilder();
        int temp = 1;
        for (int i = 0; i < target.length() - 1; i++) {
            if (target.charAt(i) == target.charAt(i + 1)) {
                temp++;
            } else {
                stringBuilder.append(target.charAt(i)).append(temp);
                temp = 1;
            }
        }
        stringBuilder.append(target.charAt(target.length() - 1)).append(temp);
        return stringBuilder.toString().length() >= target.length() ? target :
                stringBuilder.toString();
    }
}


